package 左哥算法.ch05链表;

import java.util.Arrays;
import java.util.Random;

/**
 * 跳表
 */
public class Skiplist {
    public final static int MAX_LEVEL=32;
    int currLevel;
    Node head;
    Random random=new Random();
    public Skiplist() {
        head=new Node(0,MAX_LEVEL);
        currLevel=0;
    }

    /**
     * @return:返回target的所有前驱节点
     */
    public Node[] findPreNode(int target){
        Node[] preNode = new Node[currLevel];
        Arrays.fill(preNode,head);
        Node curr = head;
        for (int level = currLevel-1; level >= 0; level--) {
            while (curr.next[level]!=null&&curr.next[level].val<target){
                curr=curr.next[level];
            }
            preNode[level]=curr;
        }
        return preNode;
    }

    public boolean search(int target) {
        Node[] preNode = findPreNode(target);
        return preNode[0].next[0]!=null&&preNode[0].next[0].val==target;
    }
    public void add(int num) {
        int newLevel=getRandom();
        Node newNode=new Node(num,newLevel);
        currLevel=Math.max(newLevel,currLevel);
        Node[] preNode = findPreNode(num);
        //将新节点插入到前驱节点之后
        for (int i = 0; i < newLevel; i++) {
            newNode.next[i]=preNode[i].next[i];
            preNode[i].next[i]=newNode;
        }
    }
    public boolean erase(int num) {
        Node[] preNode = findPreNode(num); //要删除节点的前驱节点
        Node node = preNode[0].next[0];
        if (node ==null|| node.val!=num){   //后继节点不是num
            return false;
        }
        //清除引用
        for (int i = 0; i < node.next.length; i++) {
            preNode[i].next[i]=node.next[i];
            node.next[i]=null;
        }
        return true;
    }

    public int getRandom(){
        int res=1;
        while (random.nextBoolean()&&res<=MAX_LEVEL) {
            res++;
        }
        return res;
    }
}
class Node{
    int val;
    Node[] next;

    public Node(int val,int level) {
        this.val = val;
        this.next = new Node[level];
    }
}